package com.hanxiaozhang.greedy;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈分割金条〉
 *
 * @author hanxinghua
 * @create 2021/9/23
 * @since 1.0.0
 */
public class SplitGold {

    /**
     * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管怎么切，都要花费20个铜板。
     * 一群人想整分整块金条，怎么分最省铜板?
     * 例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
     * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50；一共花费110铜板。
     * 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30；一共花费90铜板。
     * 输入一个数组，返回分割的最小代价。
     *
     * @param args
     */
    public static void main(String[] args) {

        int[] array = {10, 20, 30};
        System.out.println(splitGold1(array));
        System.out.println(splitGold2(array));

    }


    /**
     * 暴力递归
     *
     * @param array
     * @return
     */
    public static int splitGold1(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        return process(array, 0);
    }

    /**
     * @param array 剩余数组
     * @param pre   已经计算的话费
     * @return
     */
    private static int process(int[] array, int pre) {
        // 数组长度为1
        if (array.length == 1) {
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                System.out.println("pre is " + pre + " i is " + i + " j is " + j + " ans is " + (pre + array[i] + array[j]) + " ansMin is "+ans+" array is " + Arrays.toString(array));
                ans = Math.min(ans, process(copyAndMergeTwo(array, i, j), pre + array[i] + array[j]));
            }
        }
        return ans;
    }

    /**
     * i和j合并成一个元素，添加到新数组
     *
     * @param array
     * @param i
     * @param j
     * @return
     */
    private static int[] copyAndMergeTwo(int[] array, int i, int j) {
        int[] ans = new int[array.length - 1];
        int ansi = 0;
        // 不等于i,j位置，从0位置放入新的数组。
        for (int arri = 0; arri < array.length; arri++) {
            if (arri != i && arri != j) {
                ans[ansi++] = array[arri];
            }
        }
        // 最后一个位置放入， array[i] + array[j]的和
        ans[ansi] = array[i] + array[j];
        return ans;
    }

    /**
     * 使用小根堆
     *
     *
     * @param array
     * @return
     */
    public static int splitGold2(int[] array) {
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        // 把每个元素添加到优先队列
        for (int i = 0; i < array.length; i++) {
            pQ.add(array[i]);
        }
        int sum = 0;
        int cur = 0;
        // 队列大于1一直循环
        while (pQ.size() > 1) {
            // 弹出两个最小值，相加
            cur = pQ.poll() + pQ.poll();
            // 汇总
            sum += cur;
            // 将值加入队列
            pQ.add(cur);
        }
        return sum;
    }


}
